#include "big_integer.h"

big_integer::big_integer(const std::string& s)
{
   int n = s.length();
   for (long i = n; i > 0; i -= K)
   {
      if (i < K)
         digits.push_back(atoi(s.substr(0, i).c_str()));
      else
         digits.push_back(atoi(s.substr(i - K, K).c_str()));
   }
}

bool operator<(const big_integer& a, const big_integer& b)
{
   return compare(a, b, 0) < 0;
}

big_integer operator*(const big_integer& x, const int& b)
{
   assert(b <= 1e9);
   int carry = 0;
   big_integer a(x);
 
   int n = a.digits.size();
   a.digits.push_back(0);

   for (int i = 0; i <= n; i++) 
   {	   
      long long cur = carry + a.digits[i] * 1ll * b;
      a.digits[i] = static_cast<int> (cur % BASE);
      carry = static_cast<int> (cur / BASE);
   }

   while (a.digits.size() > 1 && a.digits.back() == 0)
      a.digits.pop_back();
   
   return a;
}

bool operator==(const big_integer& a, int b)
{
   if (a.digits.size() != 1)
      return false;
   
   if (a.digits[0] == b)
      return true;

   return false;
}

bool operator==(int b, const big_integer& a)
{
   return (a == b);
}

bool operator!=(int b, const big_integer& a)
{
   return !(b == a);
}

bool operator!=(const big_integer& a, int b)
{
   return (b != a);
}

int compare(const big_integer& a, const big_integer& b, int shift)
{
   if (a.digits.size() != b.digits.size() + shift)
      return (a.digits.size() - b.digits.size() - shift);

   int i = a.digits.size() - 1;
   while ((i >= shift) && (a.digits[i] == b.digits[i - shift]))
   {
      i--;
   }

   if (i >= shift)
   {
      return a.digits[i] - b.digits[i - shift];
   }

   for (int i = 0; i < shift; i++)
   {
      if (a.digits[i] > 0) 
         return 1;
   }

   return 0;
}


void subtract(big_integer& a, const big_integer& b, int shift)
{
   int n = b.digits.size();
   
   for (int i = 0; i < n; i++)
   {
      a.digits[i + shift] -= b.digits[i];
      int j = i;
      
      int nn = a.digits.size();
      while ((a.digits[j + shift] < 0) && (j < nn))
      {
         a.digits[j + shift] += BASE;
         a.digits[j + shift + 1]--;
         j++;
      }

      while (a.digits.size() > 1 && a.digits.back() == 0)
         a.digits.pop_back();
   }
}

namespace
{
   std::pair<int, big_integer> find_digit(const big_integer& remainder, const big_integer& divisor, int shift)
   {
      int low = 0;
      int high = BASE;
      big_integer c;

      while (high - 1 > low) 
      {
         c = divisor * ((high + low) / 2);

         if (compare(remainder, c, shift) > 0)
         {
            low = (high + low) / 2;
            continue;
         }

         high = (high + low) / 2;

         if (compare(remainder, c, shift) < 0)
         {
            continue;
         }

         low = high;
      }

      c = divisor * ((high + low) / 2);

      return std::make_pair((low + high) / 2, c);
   }
}

quotient_and_remainder operator/(const big_integer& a, const big_integer& b)
{
   assert(b != 0);

   big_integer remainder = a;
   int shift = a.digits.size() - b.digits.size();

   if ((shift > -1) && (compare(a, b, shift) < 0))
      shift--;

   std::vector<int> quotient;
   if (shift > -1)
      quotient.resize(quotient.size() + shift + 1, 0);
	
   while (shift >= 0)
   {
      std::pair<int, big_integer> res = find_digit(big_integer(remainder), b, shift);
      quotient[shift] = res.first;
       
      if (compare(remainder, res.second, 0) > 0)
         subtract(remainder, res.second, shift);
      else
      {
         subtract(res.second, big_integer(remainder), shift);
         remainder = res.second;
      }
		
      shift--;
   }

   if (quotient.size() == 0)
      quotient.push_back(0);
   return quotient_and_remainder(big_integer(quotient), big_integer(remainder));
}

std::ofstream& operator<<(std::ofstream& out, const big_integer& a)
{
   int n = a.digits.size();
   if (n == 0)
      return out;

   out << a.digits[n - 1];

   for (int i = n - 2; i >= 0; --i)
   {
      int len = 1;
      int x = a.digits[i];
      while (x > EXTERNAL_BASE - 1)
      {
         len++;
         x = x / EXTERNAL_BASE;
      }

      for (int j = len; j < K; j++)
         out << "0";

      out << a.digits[i];
   }

   return out;
}

std::ofstream& operator<<(std::ofstream& out, const quotient_and_remainder& a)
{
   out << a.quotient << "\n";
   out << a.remainder;

   return out;
}